import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

/**
 * 剑指 offer 2  42.连续子数组的最大和
 * 输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
 * <p>
 * 要求时间复杂度为O(n)。
 */
public class MaxSubArray {

    @Test
    public void test1() {
        Assertions.assertEquals(6, maxSubArray(new int[]{
                -2, 1, -3, 4, -1, 2, 1, -5, 4
        }));
    }


    public int maxSubArray(int[] nums) {

        int[] previousSum = new int[nums.length];

        int max = previousSum[0] = nums[0];

        for (int i = 1; i < nums.length; i++) {

            previousSum[i] = Math.max(previousSum[i - 1] + nums[i], nums[i]);

            max = Math.max(max, previousSum[i]);
        }

        return max;
    }
}
